ftp.cs.arizona.edu/ftp.cs.arizona.edu.tar/ftp.cs.arizona.edu/icon/newsgrp/group95c.txt/000084_icon-group-sender _Sat Nov 18 15:55:45 1995.msg

Internet Message Format | 1996-01-03 | 6KB

Received: by cheltenham.cs.arizona.edu; Wed, 22 Nov 1995 10:44:02 MST
To: [e-mail]
Date: 18 Nov 1995 15:55:45 +0100
From: [e-mail] (Jan-Peter de Ruiter)
Message-Id: <[e-mail]>
Organization: Max-Panck Institut f|r Psycholinguistik, Nijmegen, the Netherlands
Sender: [e-mail]
References: <485l4c$[e-mail]>
Subject: Mathematical sets in Icon (Re: Comparing sets for equality)
Errors-To: [e-mail]

In article <485l4c$[e-mail]> [e-mail] (John Shipman) writes:

   I need an Icon function to test two sets to see if they're identical.

   Is there an operator that does this, that I have somehow missed?

No, this is a problem. A few years ago we discussed this problem here
too, and Icon's definition of identical is not the mathematical
definition, because implementing it in the mathematically correct way
will decrease Icon's performance, if I remember correctly.

Your solution will only work partially. If you insert the same string
twice, Icon will think there's two elements in your set, which is not
the way it should work, if you think of sets as mathematical sets.

Here's a complete implementation that I wrote to solve this problem.
It can also be used to check if two Icon values are identical in the
sense that they have the same values (not that they refer to the same
objects). If there's anyone from the Icon project who likes to put
this extension in the IPL, please be my guest.

Greetings,

Jan

#############################################################################
# MSET LIBRARY                                                              #
#                                                                           #
# by Jan P. de Ruiter, 1992                                                 #
# Public domain software.                                                   #
#                                                                           #
# Implements the "mset" type.                                               #
#                                                                           #
# The idea of the mset type is that no two identical data-structures can be #
# present in a set, where identity is defined as "containing the same       #
# elements".                                                                #
#                                                                           #
# This seemingly radical idea is actually quite common in mathematics. :-)  #
#                                                                           #
# Definitions implicit in the procedure same_value(..,..):                  #
#                                                                           #
# TYPE              IDENTITY TEST                                           #
#                                                                           #
# all types            ===          and if this test fails...               #
#                                                                           #
# integer               =                                                   #
# real                  =                                                   #
# cset, string          ==                                                  #
# record            all fields have same value                              #
# list              all elements are the same, and the ordering is the same #
# table             same keys, and every key has the same associated value  #
# set               contain the same elements                               #
#                                                                           #
#############################################################################

#
# This is the core routine.
# It succeeds if two things have the same value(s).
#
procedure same_value(d1,d2)
    if d1 === d2 then return              # same object
    else
    if type(d1) ~== type(d2) then fail  # not the same type
    else
    if *d1 ~= *d2 then fail             # not the same size
    else
    case type(d1)  of {                 # the same type and size
       ("set"  | "table"  ) : return same_elements(sort(d1,1),sort(d2,1))
       ("list")             : return same_elements(d1,d2)
       ("real" | "integer") : return(d1 = d2)
       ("cset" | "string" ) : return(d1 == d2)
       default              : return same_elements(d1,d2) # user defined type
    }
end

#
# used in same_value:
#

procedure same_elements(l1,l2)
    if l1 === l2 then return   # same objects
    else
    if *l1 ~= *l2 then fail    # not the same size
    else {
        if *l1 = 0 then return # both lists empty
        else {
            every(i := 1 to *l1) do
                if not same_value(l1[i],l2[i]) then fail  # recursion
            return
        }
    }
end

#
# The new insert operation. Insert2 always succeeds
#
procedure insert2(S,el)
    if same_value(el,!S) then return
    return insert(S,el)
end

#
# The new member operation, that also detects equal-valued elements
#
procedure member2(S,el)
    if same_value(!S,el) then return
    fail
end

#
# The new delete operation, that detects equal-valued elements.
# Always succeeds
#
procedure delete2(S,el)
    every(t := !S) do if same_value(t,el) then return delete(S,t)
    return
end

#
# conversion of standard icon set into new mset.
#
procedure reduce(iset)
    temp := set()
    every(insert2(temp,!iset))
    return temp
end